package com.leetcode.题库;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-03-12 20:35
 */
public class 题库_0056_合并区间 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][] intervals = {{2,3},{4,5},{6,7},{8,9},{1,10}};
    int[][] merge = solution.merge(intervals);
    Arrays.stream(merge).forEach(arr -> System.out.print(Arrays.toString(arr)));
  }


  static
  class Solution {
    public int[][] merge(int[][] intervals) {
      List<Node> nodeList = new ArrayList<>();
      for (int[] ints : intervals) {
        nodeList.add(new Node(ints[0], ints[1]));
      }

      nodeList.sort((before, after) -> {
        int compare = before.start - after.start;
        return compare == 0 ? before.end - after.end : compare;
      });

      List<Node> answerNodes = new ArrayList<>();

      int left = 0;
      int right = 0;
      while (right < nodeList.size()) {
        right = left + 1;
        Node node = nodeList.get(left);
        boolean mark = true;
        while (mark && right < nodeList.size()) {
          mark = false;
          Node candidate = nodeList.get(right);
          boolean nodeEndMatch = node.end >= candidate.start && node.end <= candidate.end;
          boolean candidateEndMatch = candidate.end >= node.start && candidate.end <= node.end;
          if (nodeEndMatch || candidateEndMatch) {
            mark = true;
            ++right;
            node.end = Math.max(node.end, candidate.end);
          }
        }
        answerNodes.add(node);
        left = right;
      }

      int[][] answer = new int[answerNodes.size()][2];
      for (int i = 0; i < answer.length; ++i) {
        Node node = answerNodes.get(i);
        answer[i][0] = node.start;
        answer[i][1] = node.end;
      }
      return answer;
    }

    static class Node {
      int start;
      int end;

      Node(int start, int end) {
        this.start = start;
        this.end = end;
      }
    }

  }

}
